The field of positioning systems is highly developed with a wide variety of signal processing and computational techniques documented in the literature, some of which are implemented in ubiquitous standards, like GPS. Though the field is well developed, there remain application spaces where existing techniques are either inadequate or impractical to implement. One such area is indoor positioning and positioning within dense urban environments.
It is advantageous when existing network technologies can be adapted provide to inherent positioning and timing calibration. Such approaches leverage existing communication components (e.g., RF radios of network nodes) and device clocks to provide positioning and timing. Specific examples of this type of approach are described in Assignee's U.S. Pat. Nos. 7,876,266, 7,983,185, Published US Patent Applications 20090233621 and 20090213828, and U.S. patent application Ser. No. 13/187,723 filed Jul. 21, 2011, entitled MULTI-PATH-COMPENSATION METHODS FOR LOCATION-DETERMINATION OF MOBILE DEVICES (published as 2012-0309415), and Ser. No. 13/179,807 filed Jul. 11, 2011, entitled LOCATION AWARE INTELLIGENT TRANSPORTATION SYSTEMS (published as 2012-0309414), which are hereby incorporated by reference in their entirety (referred to as “space-time calibration patents”).
The positioning and timing schemes described in this document relate to these space-time calibration patents. Several new positioning and timing methods are disclosed, along with system architectures and data structure configurations for implementing the methods in many different network configurations.
The invention provides a method of computing positioning of a mobile device in a wi-fi network. The method comprises:
exchanging wi-fi packets among plural pairs of wi-fi nodes, including assigning local clock values to packets upon sending and receiving the packets from each of the wi-fi nodes in the pair, and communicating the local clock values in wi-fi packets exchanged between the pairs of wi-fi nodes;
capturing at least a receipt count stamp in wi-fi packet communication between a mobile device and wi-fi nodes in the plural pairs;
determining from the local clock values and the receipt count stamps, differential ranges between a mobile device and each of plural pairs of wi-fi nodes; and
determining location of the mobile device based on the differential ranges.
In various applications, multipath error presents a significant challenge to accurate positioning. Embodiments of the method estimate the error and remove it from range estimates prior to locating the mobile device, or evaluate it as part of the process of determining the mobile device location from the differential ranges.
The method scales to provide a positioning service for several mobile devices within a network at a venue, and for several positioning networks for different venues. In one embodiment, a router receives packet data from network nodes and sorts it into data structures based on mobile device ID and message ID. The router provides the data structures to a network service, such as web based cloud computing service, to provide location for each of the mobile devices.
This document details several novel methods for determining positioning and timing within networks. One inventive method for computing positioning of a mobile device comprises:                receiving a message sent from a mobile device at each of a set of network nodes at corresponding network node locations;        exchanging pings among the network nodes, including assigning local clock values to pings upon sending and receiving the pings;        from the local clock values exchanged among the network nodes, determining clock differences among the network nodes;        from the clock differences, determining path delay between the network nodes;        from data provided by the network nodes about receipt of the message and the path delays, determining pseudo range estimates between the mobile device and the network nodes; and        determining location of the mobile device by evaluating differences between candidate positions of the mobile device and the pseudo range estimates, and selecting a candidate location with minimum error criteria as the location of the mobile device.        
There are many variations and enhancements of the above methods. In one enhancement, the multipath error is estimated for the network nodes and removed from the pseudo range estimates. The multipath error is estimated for the network nodes and removed from the pseudo range estimates prior to determining the location, or is estimated and compensated for in the determining of the location of the mobile device.
There are full duplex and transmit only modes of operation. Full duplex modes are where network nodes transmit and receive pings and count stamp them. The transmit-only mode refers to cases where mobile devices transmit messages only, and do not count stamp them. Rather, receiving infrastructure nodes count stamp them and share data about the receipt of identified messages from mobile devices. In this mode, the method derives differential ranges of the network nodes to the mobile device from count stamps of the message at the network nodes. The differential ranges for sets of nodes are then used to estimate pseudo ranges between the mobile device and the nodes.
In any of the modes, full duplex exchanges between network nodes can be used to determine path delays of nodes so that the path delays can be accounted for in determining pseudo ranges.
Embodiments of our positioning methods evaluate clock value differences between pairs of network nodes over time to determine the clock differences of local clocks within the network nodes. This evaluation comprises a linear modeling of fitting clock count differences to a linear model to derive clock difference parameters among pairs of nodes. A consistency checking process, such as median approach, may be applied to clock count data before applying the linear modeling. In general, the consistency check evaluates data collected over time and removes outlier clock count data.
The process of locating the mobile device from range data is referred to as emplacement. Embodiments of emplacement evaluate variation of a differential between ranges of candidate positions of the mobile device and the pseudo range estimates (called residual), and select a location where the variation of the differential satisfies predetermined criteria. The estimated multipath error may be used to compensate for multipath error in computing the differential.
Various other multipath mitigation and compensation schemes are described. In one scheme, the multipath error is estimated by determining areas in the network with similar estimated multipath error and assigning multipath errors corresponding to the areas to the network nodes within the areas. That assigned estimate can then be used to compensate for multipath error in range calculations or emplacement associated with those nodes.
Another scheme estimates multipath error by evaluating differential range estimates of network nodes relative to the mobile device computed from the message sent to the network nodes from the mobile device, and assigning multipath error estimates to each of several pairs of nodes. For each node that is a member of a pair, the multipath estimates for the pairs can then be used to set a multipath error for the node.
In another scheme, multipath estimates are refined by averaging estimates of multipath error from un-correlated conditions. The refined estimates of multipath error are then used to compensate for multipath error in determining the mobile device location (e.g., in the emplacement process).
Further features will become apparent with reference to the following detailed description and accompanying drawings.